Date: Wed, 08 Jan 1997 20:48:52 GMT
Server: NCSA/1.4.2
Content-type: text/html

<!DOCTYPE HTML PUBLIC "-//W3O//DTD W3 HTML 2.0//EN">
<!Converted with LaTeX2HTML 95 (Thu Jan 19 1995) by Nikos Drakos (nikos@cbl.leeds.ac.uk), CBLU, University of Leeds >
<HEAD>
<TITLE>CSE 322  
Midterm Solutions  
Winter Quarter, 1996</TITLE>
</HEAD>
<BODY>
<meta name="description" value="CSE 322  
Midterm Solutions  
Winter Quarter, 1996">
<meta name="keywords" value="midtermsoln">
<meta name="resource-type" value="document">
<meta name="distribution" value="global">
<P>
 <BR> <HR><A NAME=tex2html1 HREF="node1.html"><IMG ALIGN=BOTTOM ALT="next" SRC="http://www.cs.washington.edu/general/latex2html_icons//next_motif.gif"></A>   <IMG ALIGN=BOTTOM ALT="up" SRC="http://www.cs.washington.edu/general/latex2html_icons//up_motif_gr.gif">   <IMG ALIGN=BOTTOM ALT="previous" SRC="http://www.cs.washington.edu/general/latex2html_icons//previous_motif_gr.gif">         <BR>
<B> Next:</B> <A NAME=tex2html2 HREF="node1.html">   About this document </A>
<BR> <HR> <P>
<P>
<H1>CSE 322  
Midterm Solutions  
Winter Quarter, 1996</H1>
<P><STRONG></STRONG><P>
<P><STRONG></STRONG><P>
<P>
<OL><LI>
We will use the technique given in the handout and explained by Jim
Fix to construct a regular grammar for <IMG  ALIGN=MIDDLE ALT="" SRC="img1.gif">.
Since we eventually need to generate a unique set of non-terminals for 
each <b>a</b> and <b>b</b> in the regular expression, we annotate the expression
with indices: <IMG  ALIGN=MIDDLE ALT="" SRC="img2.gif">.  These indices aren't
intended to mean anything, but we'll use them for bookeeping as we develop the grammar.  For each set of productions, we denote any starting symbol
<b>S</b> as <IMG  ALIGN=BOTTOM ALT="" SRC="img3.gif">.  If any nonterminal and its productions can be 
eliminated because it is unreachable from the starting symbol, it is 
marked with <IMG  ALIGN=MIDDLE ALT="" SRC="img4.gif">.
<P>
<IMG  ALIGN=BOTTOM ALT="" SRC="img5.gif"><IMG  ALIGN=BOTTOM ALT="" SRC="img6.gif">
<IMG  ALIGN=BOTTOM ALT="" SRC="img7.gif"><IMG  ALIGN=BOTTOM ALT="" SRC="img8.gif">
<P>
<IMG  ALIGN=BOTTOM ALT="" SRC="img9.gif"><IMG  ALIGN=BOTTOM ALT="" SRC="img10.gif">
<IMG  ALIGN=BOTTOM ALT="" SRC="img11.gif">
<P>
Thus the final grammar constructed is:
<P>
<IMG  ALIGN=BOTTOM ALT="" SRC="img12.gif">
<P>
<LI>
<IMG  ALIGN=MIDDLE ALT="" SRC="img13.gif">.
<P>
<IMG  ALIGN=BOTTOM ALT="" SRC="img14.gif">.
Each production is used once.
<P>
<LI>
<IMG  ALIGN=MIDDLE ALT="" SRC="img15.gif">.
<P>
<LI>
With start symbol <IMG  ALIGN=MIDDLE ALT="" SRC="img16.gif"> the grammar is:
<P>
<P><IMG  ALIGN=BOTTOM ALT="" SRC="img17.gif"><P>
<P>
The meaning of <IMG  ALIGN=MIDDLE ALT="" SRC="img18.gif"> is that the number of <b>a</b>'s generated by <IMG  ALIGN=MIDDLE ALT="" SRC="img19.gif"> is
equal to <IMG  ALIGN=BOTTOM ALT="" SRC="img20.gif">.
<P>
<LI> 
The fact we are trying to prove is that if <IMG  ALIGN=MIDDLE ALT="" SRC="img21.gif"> has
an equal number of <b>a</b>'s as <b>b</b>'s then <IMG  ALIGN=BOTTOM ALT="" SRC="img22.gif">.  This
will be proved by induction on <b>n</b> where <b>|x| = 2n</b>.
<OL><LI>
The basis is <b>n=0</b>.  The only string of length <b>0</b> is <IMG  ALIGN=BOTTOM ALT="" SRC="img23.gif">. 
<IMG  ALIGN=BOTTOM ALT="" SRC="img24.gif"> in one step.
<LI>
The inductive hypothesis is: If <b>w</b> is a string in <IMG  ALIGN=MIDDLE ALT="" SRC="img25.gif"> with an equal
number of <b>a</b>'s as <b>b</b>'s and <b>|w| &lt; 2n</b>, then <IMG  ALIGN=BOTTOM ALT="" SRC="img26.gif">.
<LI>
Case 1 of the induction step.  Recall that we are assuming that
<b>x</b> has an equal number of <b>a</b>'s as <b>b</b>'s, <b>|x| = 2n</b> and <b>n &gt; 0</b>.
In case 1 there is a string <b>y</b> such that <b>x =yz</b>, <b>y</b> has
an equal number of <b>a</b>'s as <b>b</b>'s, <IMG  ALIGN=MIDDLE ALT="" SRC="img27.gif">, and <IMG  ALIGN=MIDDLE ALT="" SRC="img28.gif">.
<P>
Since both <b>x</b> and  <b>y</b> have an equal number of <b>a</b>'s as <b>b</b>'s then
it must be the case that <b>z</b> does also.
Since <IMG  ALIGN=MIDDLE ALT="" SRC="img29.gif"> then <b>|y| &lt; 2n</b>.  Since <IMG  ALIGN=MIDDLE ALT="" SRC="img30.gif"> then it
must be the case that <b>|z| &lt; 2n</b>.  Thus, both <b>y</b> and <b>z</b> satisfy the
hypothesis of the inductive hypothesis. 
Hence, <IMG  ALIGN=MIDDLE ALT="" SRC="img31.gif"> and <IMG  ALIGN=BOTTOM ALT="" SRC="img32.gif">.  By using the
first production with these two derivations we have the derivation.
<P><IMG  ALIGN=BOTTOM ALT="" SRC="img33.gif"><P></OL></OL><BR> <HR>
<UL> 
<LI> <A NAME=tex2html3 HREF="node1.html#SECTION00010000000000000000">   About this document ... </A>
</UL>
<BR> <HR><A NAME=tex2html1 HREF="node1.html"><IMG ALIGN=BOTTOM ALT="next" SRC="http://www.cs.washington.edu/general/latex2html_icons//next_motif.gif"></A>   <IMG ALIGN=BOTTOM ALT="up" SRC="http://www.cs.washington.edu/general/latex2html_icons//up_motif_gr.gif">   <IMG ALIGN=BOTTOM ALT="previous" SRC="http://www.cs.washington.edu/general/latex2html_icons//previous_motif_gr.gif">         <BR>
<B> Next:</B> <A NAME=tex2html2 HREF="node1.html">   About this document </A>
<BR> <HR> <P>
<BR> <HR>
<P><ADDRESS>
<I>James Fix <BR>
Mon Feb  5 14:00:23 PST 1996</I>
</ADDRESS>
</BODY>
